#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define CAP 10
//使首元素有序
//使前两个元素有序
//。。。
//使前n个元素有序

void insert_sort(int *data,int size){
	int i = 0,j = 0;
	for(i = 1;i < size;i++){
		int inserted =data[i];
		for(j = i;j > 0;j--){
			//大于被取出数据者后移
			if(inserted < data[j-1]){
				data[j] = data[j - 1];
				}else{
				break;
					}
			}
		if(j != i) data[j] = inserted;
		}
}
void bubble_sort(int* data,int size){
	int i = 0,j = 0;
	for(i = 0; i < size - 1; i++){//趟数
		int ordered = 1;//为1无序为0有序
		for(j = 0; j < size - 1 - i;j++){//交换次数
			if(data[j+1] < data[j]){
				int swap = data[j];
				data[j] = data[j+1];
				data[j+1] = swap;
				ordered = 0;
				}
			}
		if(ordered) break;
		}
	}
//选择排序
/*
子序列里找到最小值交换到子序列的首位置
*/
void select_sort(int* data,int size){
	int i = 0;
	for(i = 0; i < size - 1; i++){
		int min = i;
		int j = 0;
		//找到子序列中最小元素的下标
		for(j = i + 1;j < size;j++){
			if(data[j] < data[min]){
				min = j;
				}
			}
		//将最小元素交换到子序列的首位置
		if(min != i){
			int swap = data[i];
			data[i] = data[min];
			data[min] = swap;
			}
		}
	}
int main(){
	//生成随机数列
	int data[10];
	srand(time(NULL));
	int i = 0;
	for(i = 0; i < CAP; i++){
		data[i] = rand() % 100;
		printf("%2d ",data[i]);
		}
	printf("\n");
	//bubble
	//bubble_sort(data,CAP);
	//insert_sort(data,CAP);
	select_sort(data,CAP);
	for(i = 0;i < CAP;i++){
		printf("%2d ",data[i]);
		}
	printf("\n");
	return 0;
	}
